package com.chj.dfs.class04;

import java.util.ArrayList;
import java.util.List;

public class Code10_GenerateParentheses {
	public static List<String> generateParenthesis(int n) {
		List<String> res = new ArrayList<>();
		dfs(res, n, n, "");
		return res;
	}

	private static void dfs(List<String> res, int left, int right, String curStr) {
		if (left == 0 && right == 0) { // 左右括号都不剩余了，说明找到了有效的括号
			res.add(curStr);
			return;
		}
		// 左括号只有剩余的时候才可以选，如果左括号的数量已经选完了，是不能再选左括号了。
		// 如果选完了左括号我们是还可以选择右括号的。
		if (left < 0)
			return;
		// 如果右括号剩余数量小于左括号剩余的数量，说明之前选择的无效
		if (right < left)
			return;
		// 选择左括号
		dfs(res, left - 1, right, curStr + "(");
		// 选择右括号
		dfs(res, left, right - 1, curStr + ")");
	}

	public static boolean valid(char[] current) {
		int balance = 0;
		for (char c : current) {
			if (c == '(')
				balance++;
			else
				balance--;
			if (balance < 0)
				return false;
		}
		return (balance == 0);
	}

	public static void generated(String item, int n, List<String> result, char[] is) {
		if (item.length() == 2 * n) {
			if (valid(item.toCharArray())) {
				result.add(item);
			}

			return;
		}

		for (int i = 0; i < is.length; i++) {
			generated(item + is[i], n, result, is);
		}

	}

	public static void generated02(String item, int left, int right, List<String> result, char[] is) {
		if (left == 0 && right == 0) {
			result.add(item);
			return;
		}

		for (int i = 0; i < is.length; i++) {
			// 左括号只有剩余的时候才可以选，如果左括号的数量已经选完了，是不能再选左括号了。
			// 如果选完了左括号我们是还可以选择右括号的。
			if (left < 0)
				return;
			// 如果右括号剩余数量小于左括号剩余的数量，说明之前选择的无效
			if (right < left)
				return;
			if (is[i] == '(') {
				generated02(item + is[i], left - 1, right, result, is);
			} else {
				generated02(item + is[i], left, right - 1, result, is);
			}
		}

	}

	public static void main(String[] args) {
		{
			List<String> sum = generateParenthesis(3);
			System.out.println(sum);
		}

		System.out.println("===========");
		{
			int n = 3;
			String item = "";

			char[] is = new char[] { '(', ')' };
			List<String> result = new ArrayList<>();
			generated(item, n, result, is);
			System.out.println(result);
		}

		System.out.println("===========");
		{
			int n = 3;
			String item = "";

			char[] is = new char[] { '(', ')' };
			List<String> result = new ArrayList<>();
			generated02(item, n, n, result, is);
			System.out.println(result);
		}
	}

//	                    输入：n = 3
//			输出：[
//			       "((()))",
//			       "(()())",
//			       "(())()",
//			       "()(())",
//			       "()()()"
//			     ]

}
